package mashibing.class4;

import java.util.Arrays;

/**
 * 归并排序(递归、非递归)
 *
 * @author yujiafan
 * @version 1.0.0
 * @create 2023-03-17
 */
public class Class4_1_Merge {

    // 递归
    public static void mergeSorted(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    public static void process(int[] arr, int L, int R) {
        if (L == R) {
            return;
        }
        int M = L + ((R - L) >> 1);
        process(arr, L, M);
        process(arr, M + 1, R);
        merge(arr, L, M, R);
    }

    // 非递归
    public static void mergeSorted1(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // 步长
        int step = 1;
        int N = arr.length;
        while (step < N) {
            int L = 0;
            while (L < N) {
                int M = L + step - 1;
                if (M >= N) {
                    break;
                }
                int R = Math.min(M + step, N - 1);
                merge(arr, L, M, R);
                L = R + 1;
            }
            if (step > N / 2) {
                break;
            }
            step = step <<1;
        }
    }

    public static void merge(int[] arr, int L, int M, int R) {
        int[] help = new int[R - L + 1];
        int index = 0;
        int p1 = L;
        int p2 = M + 1;
        while (p1 <= M && p2 <= R) {
            help[index++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= M) {
            help[index++] = arr[p1++];
        }
        while (p2 <= R) {
            help[index++] = arr[p2++];
        }
        for (int i = 0; i < help.length; i++) {
            arr[L + i] = help[i];
        }
    }

    public static void main(String[] args) {
        int[] arr = {6, 1, 8, 3, 2, 5, 1, 2, 3, 6, 4};
        System.out.println(Arrays.toString(arr));
//        MergeSorted(arr);
        mergeSorted1(arr);
        System.out.println(Arrays.toString(arr));
    }
}
